DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2021.43

Reliable Spanners for Metric Spaces

Authors: Sariel Har-Peled, Manor Mendel, and Dániel Oláh

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract

A spanner is reliable if it can withstand large, catastrophic failures in the network. More precisely, any failure of some nodes can only cause a small damage in the remaining graph in terms of the dilation, that is, the spanner property is maintained for almost all nodes in the residual graph. Constructions of reliable spanners of near linear size are known in the low-dimensional Euclidean settings. Here, we present new constructions of reliable spanners for planar graphs, trees and (general) metric spaces.

Cite as

Sariel Har-Peled, Manor Mendel, and Dániel Oláh. Reliable Spanners for Metric Spaces. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 43:1-43:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{harpeled_et_al:LIPIcs.SoCG.2021.43,
  author =	{Har-Peled, Sariel and Mendel, Manor and Ol\'{a}h, D\'{a}niel},
  title =	{{Reliable Spanners for Metric Spaces}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{43:1--43:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.43},
  URN =		{urn:nbn:de:0030-drops-138423},
  doi =		{10.4230/LIPIcs.SoCG.2021.43},
  annote =	{Keywords: Spanners, reliability}
}

Search Results

Documents authored by Mendel, Manor

Reliable Spanners for Metric Spaces

Abstract

Cite as

Thanks for your feedback!

Could not send message